import collections
import random


class DesignProblem:
    class LRUCache:
        def __init__(self, capacity):
            """
            LRU缓存算法（Least Recently Used Cache Algorithm）

            参数:
            capacity (int): 缓存容量

            实现步骤:
            1. 初始化缓存容量、字典cache和双向链表linked_list
            2. 双向链表的节点使用collections.OrderedDict实现，可以按照访问顺序进行排序
            3. 实现get方法，从缓存中获取值并返回，若不存在则返回-1，并将访问的节点移到链表末尾
            4. 实现put方法，若键存在则更新其值并将访问的节点移到链表末尾，若不存在则在缓存中插入新的键值对，
               若缓存已满，则删除链表头部的最久未使用节点，再插入新的键值对

            """

            # 步骤 1: 初始化缓存容量、字典cache和双向链表linked_list
            self.capacity = capacity
            self.cache = {}
            self.linked_list = collections.OrderedDict()

        def get(self, key):
            """
            获取缓存中键对应的值

            参数:
            key (int): 键

            返回:
            int: 键对应的值，若键不存在则返回-1

            """

            # 步骤 3: 获取缓存中键对应的值并返回，若不存在则返回-1，并将访问的节点移到链表末尾
            if key not in self.cache:
                return -1
            value = self.cache[key]
            del self.linked_list[key]
            self.linked_list[key] = value
            return value

        def put(self, key, value):
            """
            向缓存中插入新的键值对或更新已有键的值

            参数:
            key (int): 键
            value (int): 值

            返回:
            None

            """

            # 步骤 4: 若键存在则更新其值并将访问的节点移到链表末尾，若不存在则在缓存中插入新的键值对
            if key in self.cache:
                del self.linked_list[key]
            elif len(self.cache) >= self.capacity:
                # 若缓存已满，则删除链表头部的最久未使用节点
                oldest_key = next(iter(self.linked_list))
                del self.cache[oldest_key]
                del self.linked_list[oldest_key]
            self.cache[key] = value
            self.linked_list[key] = value

    class MinStack:
        def __init__(self):
            """
            最小栈算法（Minimum Stack Algorithm）

            实现步骤:
            1. 初始化数据栈stack和辅助栈min_stack
            2. 实现push方法，在数据栈中压入元素，并在辅助栈中压入当前最小元素
            3. 实现pop方法，同时从数据栈和辅助栈弹出栈顶元素
            4. 实现top方法，返回数据栈的栈顶元素
            5. 实现getMin方法，返回辅助栈的栈顶元素，即当前最小元素

            """

            # 步骤 1: 初始化数据栈stack和辅助栈min_stack
            self.stack = []
            self.min_stack = []

        def push(self, x):
            """
            将元素压入栈中

            参数:
            x (int): 元素值

            返回:
            None

            """

            # 步骤 2: 在数据栈中压入元素，并在辅助栈中压入当前最小元素
            self.stack.append(x)
            if not self.min_stack or x <= self.min_stack[-1]:
                self.min_stack.append(x)

        def pop(self):
            """
            弹出栈顶元素

            参数:
            None

            返回:
            None

            """

            # 步骤 3: 同时从数据栈和辅助栈弹出栈顶元素
            if self.stack.pop() == self.min_stack[-1]:
                self.min_stack.pop()

        def top(self):
            """
            获取栈顶元素的值

            参数:
            None

            返回:
            int: 栈顶元素的值

            """

            # 步骤 4: 返回数据栈的栈顶元素
            return self.stack[-1]

        def getMin(self):
            """
            获取栈中的最小元素的值

            参数:
            None

            返回:
            int: 栈中的最小元素的值

            """

            # 步骤 5: 返回辅助栈的栈顶元素，即当前最小元素
            return self.min_stack[-1]

    class RandomizedSet:
        def __init__(self):
            """
            常数时间插入、删除和获取随机元素的数据结构算法（Constant Time Insert, Delete, and Get Random Element Algorithm）

            实现步骤:
            1. 初始化集合set和列表list
            2. 实现insert方法，若元素已存在则返回False，否则将元素插入集合和列表中，并返回True
            3. 实现remove方法，若元素不存在则返回False，否则从集合和列表中删除元素，并返回True
            4. 实现getRandom方法，随机选择列表中的元素并返回

            """

            # 步骤 1: 初始化集合set和列表list
            self.set = set()
            self.list = []

        def insert(self, val):
            """
            向集合中插入元素

            参数:
            val (int): 元素值

            返回:
            bool: 插入成功返回True，若元素已存在返回False

            """

            # 步骤 2: 若元素已存在则返回False，否则将元素插入集合和列表中，并返回True
            if val in self.set:
                return False
            self.set.add(val)
            self.list.append(val)
            return True

        def remove(self, val):
            """
            从集合中删除元素

            参数:
            val (int): 元素值

            返回:
            bool: 删除成功返回True，若元素不存在返回False

            """

            # 步骤 3: 若元素不存在则返回False，否则从集合和列表中删除元素，并返回True
            if val not in self.set:
                return False
            self.set.remove(val)
            self.list.remove(val)
            return True

        def getRandom(self):
            """
            获取集合中的随机元素

            参数:
            None

            返回:
            int: 随机选择的元素

            """

            # 步骤 4: 随机选择列表中的元素并返回
            return random.choice(self.list)


if __name__ == '__main__':
    # 示例调用LRU缓存算法
    lru_cache = DesignProblem.LRUCache(2)
    lru_cache.put(1, 1)
    lru_cache.put(2, 2)
    print("获取缓存中键1对应的值:", lru_cache.get(1))  # 返回1
    lru_cache.put(3, 3)
    print("获取缓存中键2对应的值:", lru_cache.get(2))  # 返回-1
    lru_cache.put(4, 4)
    print("获取缓存中键1对应的值:", lru_cache.get(1))  # 返回-1
    print("获取缓存中键3对应的值:", lru_cache.get(3))  # 返回3
    print("获取缓存中键4对应的值:", lru_cache.get(4))  # 返回4
    """
    示例输出结果:
    获取缓存中键1对应的值: 1
    获取缓存中键2对应的值: -1
    获取缓存中键1对应的值: -1
    获取缓存中键3对应的值: 3
    获取缓存中键4对应的值: 4
    """

    # 示例调用最小栈算法
    min_stack = DesignProblem.MinStack()
    min_stack.push(-2)
    min_stack.push(0)
    min_stack.push(-3)
    print("获取栈中的最小元素:", min_stack.getMin())  # 返回-3
    min_stack.pop()
    print("获取栈顶元素的值:", min_stack.top())  # 返回0
    print("获取栈中的最小元素:", min_stack.getMin())  # 返回-2
    """
    示例输出结果:
    获取栈中的最小元素: -3
    获取栈顶元素的值: 0
    获取栈中的最小元素: -2
    """

    # 示例调用常数时间插入、删除和获取随机元素的数据结构算法
    random_set = DesignProblem.RandomizedSet()
    print("插入元素1是否成功:", random_set.insert(1))  # 返回True
    print("删除元素2是否成功:", random_set.remove(2))  # 返回False
    print("插入元素2是否成功:", random_set.insert(2))  # 返回True
    print("获取随机元素:", random_set.getRandom())  # 返回1或2，概率相等
    print("删除元素1是否成功:", random_set.remove(1))  # 返回True
    print("插入元素2是否成功:", random_set.insert(2))  # 返回False
    print("获取随机元素:", random_set.getRandom())  # 返回2
    """
    示例输出结果:
    插入元素1是否成功: True
    删除元素2是否成功: False
    插入元素2是否成功: True
    获取随机元素: 1或2，概率相等
    删除元素1是否成功: True
    插入元素2是否成功: False
    获取随机元素: 2
    """
